6 Transformação Linear

Modelos lineares combinam atributos por uma soma ponderada. Essa simplicidade favorece interpretação e otimização, mas uma fronteira linear no espaço original não representa todos os padrões. O XOR e uma classe cercada por outra são exemplos imediatos.

Podemos ampliar a classe de funções sem abandonar os algoritmos lineares transformando a representação de cada entrada:

\[ \phi:X\longrightarrow Z, \qquad x\longmapsto\phi(x). \]

O modelo passa a calcular

\[ h_w(x)=h_0\!\left(w^{\mathsf T}\phi(x)\right), \tag{6.1}\]

em que \(h_0\) pode ser o sinal, a identidade ou a sigmoide. O modelo é linear nos atributos transformados e nos parâmetros \(w\), embora seja não linear em relação à entrada original.

O nome do capítulo

Neste contexto, “linearização” significa representar uma relação não linear por um modelo linear em novas características. O mapa \(\phi\) não precisa ser uma transformação linear no sentido estrito da álgebra linear; mapas polinomiais, por exemplo, são não lineares.

6.1 Visão geral da transformação de atributos

6.1.1 Exemplo radial

Considere pontos no plano rotulados pela distância à origem:

\[ y= \begin{cases} +1,&x_1^2+x_2^2<r^2,\\ -1,&x_1^2+x_2^2>r^2. \end{cases} \]

Nenhuma reta separa a região interna da externa. Entretanto, com

\[ \phi(x_1,x_2)=x_1^2+x_2^2, \]

o problema torna-se unidimensional: basta comparar \(\phi(x)\) com o limiar \(r^2\).

Uma fronteira circular no espaço original torna-se um limiar linear após a transformação radial.

Não precisamos inverter \(\phi\) depois do treinamento. Para prever um novo exemplo \(x\), calculamos \(\phi(x)\) e aplicamos o modelo aprendido. A saída continua se referindo ao exemplo original.

6.1.2 Transformação da amostra

Para

\[ D=\{(x_1,y_1),\ldots,(x_N,y_N)\}, \]

a amostra transformada é

\[ \phi(D) =\{(\phi(x_1),y_1),\ldots,(\phi(x_N),y_N)\}. \]

Os rótulos não mudam. O algoritmo linear recebe \(\phi(x_n)\) como seus atributos e escolhe

\[ w^*\in\operatorname*{arg\,min}_{w} \frac1N\sum_{n=1}^{N} \ell\!\left( h_0(w^{\mathsf T}\phi(x_n)),y_n \right). \tag{6.2}\]

A hipótese final no domínio original é a composição \(h_{w^*}=h_0\circ(w^{*\mathsf T}\phi)\).

6.1.3 Exemplo polinomial

Para duas entradas, um mapa quadrático completo pode ser

\[ \phi(x_1,x_2) =\left(1,x_1,x_2,x_1^2,x_1x_2,x_2^2\right). \]

Uma pontuação linear em \(\phi(x)\) é

\[ w_0+w_1x_1+w_2x_2+w_3x_1^2+w_4x_1x_2+w_5x_2^2, \]

um polinômio quadrático no espaço original. Dependendo dos coeficientes, sua fronteira de nível pode ser elipse, parábola, hipérbole ou um caso degenerado.

6.1.4 O que permanece linear?

É útil distinguir três espaços:

Espaço	Objeto	Pode ser não linear?
entrada original	\(x\)	sim, a fronteira pode ser curva
características	\(\phi(x)\)	o mapa pode ser não linear
parâmetros	\(w^{\mathsf T}\phi(x)\)	é linear em \(w\)

Essa última linearidade permite reutilizar Perceptron, mínimos quadrados e regressão logística sem mudar sua estrutura matemática.

6.1.5 A transformação faz parte do modelo

Treino, validação, teste e produção devem usar exatamente o mesmo mapa. Se \(\phi\) depende de parâmetros estimados — médias, desvios, categorias, componentes principais — esses parâmetros devem ser aprendidos apenas no treino e armazenados com o modelo.

import numpy as np


def mapa_quadratico(X):
    """Transforma uma matriz com duas colunas."""
    x1 = X[:, 0]
    x2 = X[:, 1]
    return np.column_stack([
        np.ones(len(X)),
        x1,
        x2,
        x1**2,
        x1 * x2,
        x2**2,
    ])

Aplicar transformações diferentes entre treinamento e predição é um erro de contrato de dados, mesmo quando as dimensões coincidem.

6.1.6 Capacidade e custo

Transformar pode facilitar o ajuste, mas aumenta a capacidade da classe. Para \(d\) atributos, o número de monômios de grau até \(q\) é

\[ \binom{d+q}{q}. \]

Com \(d=100\) e \(q=2\), já são \(\binom{102}{2}=5\,151\) características incluindo o termo constante. Isso aumenta memória, tempo e risco de sobreajuste.

Regularização e validação tornam-se especialmente importantes. Uma transformação que reduz o erro de treinamento pode piorar o erro fora da amostra.

6.1.7 Transformações explícitas e implícitas

Há duas estratégias:

explícita: calcular e armazenar \(\phi(x)\);
implícita: calcular apenas produtos \(\phi(x)^{\mathsf T}\phi(x')\) por meio de um núcleo (kernel).

O artifício do núcleo será útil quando a dimensão de \(Z\) for muito grande ou até infinita, desde que o algoritmo dependa dos dados por produtos escalares.

6.1.8 Limitações

A transformação adequada depende da estrutura do problema.
Muitas características podem amplificar ruído e redundância.
Polinômios de grau alto podem extrapolar de forma extrema.
Um mapa fixo pode não capturar invariâncias relevantes.
Interpretar coeficientes transformados exige considerar toda a composição, não pesos isolados.

6.1.8.1 Questões iniciais

Em que sentido Equation 6.1 é linear e em que sentido pode ser não linear?
Por que não precisamos calcular \(\phi^{-1}\) para fazer previsões?
Quantos monômios de grau até dois existem para \(d=10\)?
Dê um exemplo de transformação que dependeria de estatísticas do treino e poderia causar vazamento de dados.
Explique por que melhorar o ajuste não prova melhora de generalização.

6.2 Linearizar Elipses em torno da origem

Suponha que os exemplos positivos ocupem o interior de uma elipse centrada na origem e os negativos fiquem do lado de fora. No plano original, a fronteira é curva e não pode ser representada por um único Perceptron linear nos atributos \((x_1,x_2)\).

Uma elipse alinhada aos eixos, com semieixos \(a,b>0\), satisfaz

\[ \frac{x_1^2}{a^2}+\frac{x_2^2}{b^2}=1. \tag{6.3}\]

Para um círculo de raio \(r\), temos \(a=b=r\) e a equação é \(x_1^2+x_2^2=r^2\). O quadrado no raio é indispensável.

6.2.1 Da elipse à reta

Defina

\[ \phi(x_1,x_2)=(z_1,z_2)=(x_1^2,x_2^2). \]

No espaço transformado, Equation 6.3 torna-se

\[ \frac{z_1}{a^2}+\frac{z_2}{b^2}=1, \]

que é a equação de uma reta. A classificação “interior positivo” pode ser escrita como

\[ h(x) =\operatorname{sinal}_{+}\!\left( 1-\frac{x_1^2}{a^2}-\frac{x_2^2}{b^2} \right). \tag{6.4}\]

No vetor homogêneo

\[ \widetilde\phi(x)=(1,x_1^2,x_2^2), \]

os pesos são

\[ w=\left(1,-\frac1{a^2},-\frac1{b^2}\right), \]

e Equation 6.4 assume a forma linear \(h(x)=\operatorname{sinal}_{+}(w^{\mathsf T}\widetilde\phi(x))\).

A elipse no espaço original corresponde a uma reta no espaço das coordenadas quadradas.

O espaço transformado acessível satisfaz \(z_1,z_2\geq0\); não ocupamos todo \(\mathbb R^2\). Isso não impede o classificador, mas lembra que \(\phi\) pode perder informação: os pontos \((x_1,x_2)\), \((-x_1,x_2)\) e outras mudanças de sinal possuem a mesma imagem.

6.2.2 Aprendendo a elipse

No exemplo anterior, \(a\) e \(b\) pareciam conhecidos. Em aprendizado, fornecemos os atributos \((1,x_1^2,x_2^2)\) e deixamos o algoritmo estimar

\[ g(z)=w_0+w_1z_1+w_2z_2. \]

Quando \(w_0>0\) e \(w_1,w_2<0\), a fronteira \(g(z)=0\) corresponde a

\[ \frac{x_1^2}{-w_0/w_1} +\frac{x_2^2}{-w_0/w_2}=1, \]

com

\[ a=\sqrt{-\frac{w_0}{w_1}}, \qquad b=\sqrt{-\frac{w_0}{w_2}}. \]

Um classificador linear não impõe automaticamente esses sinais. Para outros valores, a fronteira pode ser vazia, ilimitada ou classificar o exterior como positivo. A interpretação geométrica deve ser feita após o ajuste.

6.2.3 Elipses giradas

Uma elipse centrada na origem e não necessariamente alinhada aos eixos é descrita por

\[ x^{\mathsf T}Ax=1, \]

em que \(A\) é uma matriz simétrica positiva definida. Em duas dimensões,

\[ x^{\mathsf T}Ax =a_{11}x_1^2+2a_{12}x_1x_2+a_{22}x_2^2. \]

Precisamos então do termo cruzado:

\[ \phi(x_1,x_2) =\left(1,x_1^2,x_1x_2,x_2^2\right). \]

O coeficiente de \(x_1x_2\) permite girar os eixos principais da elipse. Sem ele, a classe contém apenas elipses alinhadas aos eixos.

6.2.4 Elipses fora da origem

Uma elipse centrada em \(c=(c_1,c_2)\) satisfaz

\[ (x-c)^{\mathsf T}A(x-c)=1. \]

Ao expandir, surgem termos quadráticos, lineares e constante. Por isso, o mapa quadrático completo

\[ \phi(x_1,x_2) =\left(1,x_1,x_2,x_1^2,x_1x_2,x_2^2\right) \]

representa cônicas transladadas. A presença desses seis atributos não garante que toda fronteira aprendida seja uma elipse; coeficientes podem produzir parábolas, hipérboles ou formas degeneradas.

6.2.5 Igualdade dos erros após a composição

Se \(g\) é uma hipótese no espaço transformado e

\[ h=g\circ\phi, \]

então, para todo exemplo, \(h(x_n)=g(\phi(x_n))\). Usando a mesma perda,

\[ E_D(h) =\frac1N\sum_n\ell(h(x_n),y_n) =E_{\phi(D)}(g). \]

Não há “ida e volta” geométrica: a igualdade decorre simplesmente de aplicar a composição aos mesmos exemplos e rótulos.

6.2.6 Capacidade da classe transformada

Se \(\mathcal G\) é a classe de separadores lineares em \(Z\) e \(\phi\) é fixado, a classe no domínio original é

\[ \mathcal H_\phi =\{g\circ\phi:g\in\mathcal G\}. \]

Como padrões realizados por \(\mathcal H_\phi\) correspondem a padrões de \(\mathcal G\) sobre imagens \(\phi(x)\),

\[ d_{\mathrm{VC}}(\mathcal H_\phi) \leq d_{\mathrm{VC}}(\mathcal G). \]

Para \(\phi(x)=(x_1^2,x_2^2)\) e separadores afins em duas dimensões, \(d_{\mathrm{VC}}(\mathcal G)=3\), portanto \(d_{\mathrm{VC}}(\mathcal H_\phi)\leq3\). A desigualdade pode ser estrita porque as imagens ficam restritas ao primeiro quadrante e pontos distintos podem coincidir após o mapeamento.

Se escolhemos entre muitos mapas usando os dados, a classe efetiva é a união das classes associadas. Isso não é proibido, mas sua complexidade deve ser contabilizada e a seleção deve usar validação apropriada.

6.2.7 Implementação

import numpy as np


def atributos_elipse(X, girada=False, transladada=False):
    X = np.asarray(X, dtype=float)
    x1, x2 = X[:, 0], X[:, 1]
    colunas = [np.ones(len(X))]

    if transladada:
        colunas.extend([x1, x2])

    colunas.append(x1**2)
    if girada:
        colunas.append(x1 * x2)
    colunas.append(x2**2)
    return np.column_stack(colunas)

A ordem das colunas deve ser armazenada com o modelo. Alterá-la na predição preserva a dimensão, mas associa cada peso ao atributo errado.

6.2.7.1 Exercícios

Corrija o classificador se a classe positiva estiver fora da elipse.
Derive \(a\) e \(b\) a partir de \((w_0,w_1,w_2)\) sob os sinais adequados.
Expanda \((x-c)^{\mathsf T}A(x-c)\) e identifique os seis coeficientes.
Mostre que \(x_1x_2\) muda de sinal sob a reflexão \((x_1,x_2)\mapsto(-x_1,x_2)\), ao contrário dos quadrados.
Explique por que selecionar o grau polinomial no conjunto de teste produz uma avaliação otimista.

6.3 Generalização da Transformação

O exemplo da elipse ilustra uma ideia mais ampla: podemos construir um novo vetor com funções das coordenadas originais e, depois, aplicar a esse vetor um algoritmo linear. Se \(x\in\mathbb R^d\), uma transformação de atributos tem a forma

\[ \phi:\mathbb R^d\longrightarrow\mathbb R^{d'}, \qquad x\longmapsto\phi(x). \]

O número \(d'\) não precisa ser igual a \(d\). Ele pode ser menor, como em redução de dimensionalidade, ou maior, quando criamos interações e termos não lineares.

6.3.1 Transformação polinomial

Uma transformação polinomial de grau máximo \(Q\) reúne todos os monômios

\[ x_1^{\alpha_1}x_2^{\alpha_2}\cdots x_d^{\alpha_d} \quad\text{tais que}\quad \alpha_j\in\mathbb N_0 \quad\text{e}\quad \sum_{j=1}^d\alpha_j\leq Q. \]

O vetor \(\alpha=(\alpha_1,\ldots,\alpha_d)\) é chamado multiíndice e \(|\alpha|=\sum_j\alpha_j\) é o grau total do monômio. Para \(d=2\) e \(Q=2\), por exemplo,

\[ \phi_2(x_1,x_2) =\left(1,x_1,x_2,x_1^2,x_1x_2,x_2^2\right). \tag{6.5}\]

Uma função linear nesse novo vetor produz

\[ w^{\mathsf T}\phi_2(x) =w_0+w_1x_1+w_2x_2+w_3x_1^2+w_4x_1x_2+w_5x_2^2, \]

isto é, um polinômio quadrático no espaço original. O modelo é não linear em \(x\), mas continua linear nos parâmetros \(w\). Essa distinção permite usar regressão linear, regressão logística ou outros algoritmos lineares após a transformação.

6.3.2 Quantos atributos são criados?

O número de monômios de grau exatamente \(q\) em \(d\) variáveis é

\[ \binom{d+q-1}{q}. \]

Somando os graus de \(0\) a \(Q\), obtemos

\[ m(d,Q)=\sum_{q=0}^Q\binom{d+q-1}{q} =\binom{d+Q}{Q}. \tag{6.6}\]

Essa contagem inclui o termo constante. Se o viés for tratado separadamente, a dimensão do vetor sem a constante será

\[ d'=\binom{d+Q}{Q}-1. \]

Para duas variáveis,

\[ d'=\binom{Q+2}{Q}-1 =\frac{Q(Q+3)}2. \]

Assim, com \(d=2\), os graus \(Q=1,2,3,4\) geram, respectivamente, 3, 6, 10 e 15 coeficientes quando contamos o termo constante.

O aumento do grau cria novas interações e eleva rapidamente a dimensão do espaço de atributos.

Em dimensões maiores, o crescimento combinatório é mais severo. Para \(d=20\) e \(Q=3\), Equation 6.6 fornece \(\binom{23}{3}=1771\) coeficientes. Uma matriz de projeto com \(N\) exemplos pode, portanto, passar de \(N\times20\) para \(N\times1771\).

6.3.3 Expressividade, generalização e custo

Ao aumentar \(Q\), a classe de hipóteses contém fronteiras mais flexíveis. Como as classes polinomiais são aninhadas, o menor erro de treinamento não pode aumentar: um modelo de grau \(Q+1\) pode sempre atribuir peso zero aos novos termos. Isso não significa que o erro fora da amostra sempre diminua.

Três efeitos devem ser considerados:

Aproximação: graus maiores podem representar relações que um modelo simples não consegue capturar.
Estimação: mais parâmetros tornam o ajuste mais sensível às particularidades e ao ruído da amostra.
Computação: armazenar a matriz transformada e calcular produtos, gradientes ou inversas passa a exigir mais memória e tempo.

Para separadores afins em \(\mathbb R^{d'}\), a dimensão VC da classe linear completa é \(d'+1\). Porém, a classe composta \(\{g\circ\phi:g\in\mathcal G\}\) pode ter dimensão VC menor, pois os vetores \(\phi(x)\) ocupam apenas uma parte estruturada do espaço transformado. Ainda assim, o crescimento de \(d'\) é um bom alerta para o risco de sobreajuste.

6.3.4 Como escolher o grau

O grau \(Q\) é um hiperparâmetro. Uma prática adequada é:

separar os dados de teste e não usá-los na escolha;
comparar os graus candidatos por validação ou validação cruzada;
ajustar no conjunto de treino qualquer normalização necessária;
aplicar exatamente a mesma transformação na validação e no teste;
selecionar o grau e a regularização em conjunto.

A padronização merece atenção. Se \(x_j\) tiver valores grandes, \(x_j^Q\) pode ficar numericamente enorme. Em geral, padronizamos as variáveis originais usando estatísticas do treino e só então geramos os termos polinomiais. Regularização \(L_2\) ou \(L_1\) também ajuda a controlar coeficientes e reduzir variância.

Evite vazamento de dados

Média, desvio-padrão, grau e força de regularização não devem ser escolhidos com informação do conjunto de teste. Em uma validação cruzada, toda a transformação precisa ser ajustada novamente dentro de cada partição de treino.

6.3.5 Implementação sem bibliotecas especializadas

O exemplo a seguir constrói 1 para uma matriz com duas colunas:

import numpy as np


def atributos_quadraticos_2d(X):
    X = np.asarray(X, dtype=float)
    if X.ndim != 2 or X.shape[1] != 2:
        raise ValueError("X deve ter formato (n_amostras, 2)")

    x1, x2 = X[:, 0], X[:, 1]
    return np.column_stack([
        np.ones(len(X)),
        x1,
        x2,
        x1**2,
        x1 * x2,
        x2**2,
    ])

Em aplicações reais, uma pipeline deve guardar a ordem das colunas e os parâmetros de normalização. Gerar os mesmos atributos em ordem diferente durante a predição produz resultados incorretos sem necessariamente causar erro de dimensão.

6.3.5.1 Exercícios

Liste todos os monômios de grau máximo \(3\) em duas variáveis.
Calcule \(m(5,2)\) e interprete a diferença entre contar ou não o termo constante.
Mostre por que o erro mínimo de treinamento não aumenta quando se passa do grau \(Q\) para \(Q+1\).
Para \(x=(2,-3)\), calcule manualmente \(\phi_2(x)\) na ordem usada em
Explique por que padronizar toda a base antes da validação cruzada constitui vazamento de dados.

6.4 O Artifício do Núcleo

Transformações explícitas podem criar milhares — ou infinitos — atributos. Entretanto, alguns algoritmos nunca precisam acessar cada coordenada de \(\phi(x)\) separadamente: eles utilizam apenas produtos escalares entre exemplos transformados. O artifício do núcleo, também chamado truque do kernel, explora exatamente essa situação.

Uma função núcleo é calculada no espaço de entrada:

\[ K:X\times X\longrightarrow\mathbb R, \qquad K(x,z)=\langle\phi(x),\phi(z)\rangle_{\mathcal F}, \tag{6.7}\]

em que \(\mathcal F\) é o espaço de atributos. Se existe uma expressão direta e barata para \(K(x,z)\), podemos obter o produto escalar sem construir os vetores \(\phi(x)\) e \(\phi(z)\).

O núcleo calcula diretamente, no espaço original, o mesmo produto escalar que seria obtido após a transformação explícita.

O ganho não vem simplesmente do fato de \(X\) ter dimensão menor. Ele depende de duas condições: o núcleo deve ser barato de avaliar e o algoritmo deve poder ser formulado apenas em termos desses produtos escalares. Métodos de margens, como máquinas de vetores de suporte, são o exemplo clássico.

6.4.1 Princípio

Considere uma amostra \(D=\{(x_i,y_i)\}_{i=1}^N\). Em muitos problemas regularizados, a solução no espaço de atributos pode ser escrita como

\[ w=\sum_{i=1}^N\alpha_i\phi(x_i). \tag{6.8}\]

Para prever em um novo ponto \(x\), calculamos

\[ \begin{aligned} f(x) &=\langle w,\phi(x)\rangle+b\\ &=\sum_{i=1}^N\alpha_i \langle\phi(x_i),\phi(x)\rangle+b\\ &=\sum_{i=1}^N\alpha_iK(x_i,x)+b. \end{aligned} \tag{6.9}\]

Observe a mudança de representação. No método primal, armazenamos as coordenadas de \(w\); na representação dual, armazenamos coeficientes \(\alpha_i\) associados aos exemplos de treino. O núcleo recebe dois pontos do domínio, e não um vetor de pesos e um ponto.

Durante o treinamento, os produtos entre todos os pares formam a matriz de Gram:

\[ G_{ij}=K(x_i,x_j), \qquad G\in\mathbb R^{N\times N}. \]

Essa matriz resume a geometria da amostra no espaço de atributos. Sua entrada \(G_{ij}\) mede a similaridade induzida pelo núcleo entre os exemplos \(x_i\) e \(x_j\).

6.4.2 Exemplo: núcleo polinomial quadrático

Em duas dimensões, tome

\[ K(x,z)=(1+x^{\mathsf T}z)^2. \]

Expandindo,

\[ K(x,z) =1+2x_1z_1+2x_2z_2+x_1^2z_1^2 +2x_1x_2z_1z_2+x_2^2z_2^2. \]

Essa expressão é o produto escalar associado ao mapa

\[ \phi(x)= \left(1,\sqrt2x_1,\sqrt2x_2,x_1^2, \sqrt2x_1x_2,x_2^2\right). \]

Logo, podemos calcular um produto em seis dimensões usando somente \(x^{\mathsf T}z\) no espaço original. Os fatores \(\sqrt2\) são necessários para que o coeficiente dos termos cruzados seja exatamente \(2\).

6.4.3 Quando o artifício se aplica?

Não basta que a função de perda contenha \(w^{\mathsf T}x\). É preciso reescrever o procedimento de treinamento e a predição em termos de produtos entre exemplos, como em Equation 6.8 e Equation 6.9. SVMs, regressão ridge em forma dual e PCA com núcleo possuem formulações desse tipo. Um código primal comum de regressão logística não aceita um núcleo automaticamente; seria necessária uma formulação ou um algoritmo apropriado.

Há também uma troca computacional. A transformação explícita costuma custar em função de \(d'\), enquanto o método de núcleo armazena uma matriz \(N\times N\). Para amostras muito grandes, o custo de memória \(O(N^2)\) e o custo do treinamento podem superar a economia obtida ao não materializar \(\phi(x)\). Portanto, núcleos são especialmente atraentes quando \(d'\) é enorme e \(N\) ainda é administrável.

import numpy as np


def matriz_gram_polinomial(X, grau=2, constante=1.0):
    X = np.asarray(X, dtype=float)
    return (constante + X @ X.T) ** grau

Para uma matriz X de formato (N, d), o resultado tem formato (N, N). Em uma implementação robusta, os mesmos parâmetros do núcleo usados no treino devem ser preservados para a predição.

6.4.3.1 Exercícios

Verifique manualmente o valor de \(K(x,z)\) para \(x=(1,2)\) e \(z=(3,-1)\) usando tanto a fórmula direta quanto o mapa explícito.
Explique a diferença entre as dimensões de \(X\), \(\phi(X)\) e da matriz de Gram.
Mostre que a matriz de Gram de um núcleo simétrico também é simétrica.
Compare a memória de uma matriz explícita \(N\times d'\) com a da matriz de Gram \(N\times N\) quando \(N=10\,000\) e \(d'=500\).

6.4.4 Teorema de Mercer

Nem toda função de similaridade pode substituir um produto escalar. Para ser um núcleo real válido, \(K:X\times X\to\mathbb R\) deve satisfazer duas propriedades fundamentais.

Primeiro, deve ser simétrico:

\[ K(x,z)=K(z,x). \]

Segundo, deve ser semidefinido positivo: para qualquer quantidade finita de pontos \(x_1,\ldots,x_N\in X\) e quaisquer coeficientes reais \(c_1,\ldots,c_N\),

\[ \sum_{i=1}^N\sum_{j=1}^N c_i c_j K(x_i,x_j)\geq0. \tag{6.10}\]

Se \(G\) é a matriz de Gram, essa condição equivale a

\[ c^{\mathsf T}Gc\geq0 \quad\text{para todo }c\in\mathbb R^N. \]

Como \(G\) é simétrica, isso também equivale a dizer que todos os seus autovalores são não negativos. Pequenos autovalores negativos podem aparecer numericamente por arredondamento; valores negativos relevantes indicam que a função ou a implementação não produz uma matriz semidefinida positiva naquela amostra.

6.4.5 Por que a positividade é necessária?

Se existe um mapa \(\phi\) tal que \(K(x,z)=\langle\phi(x),\phi(z)\rangle\), então

\[ \begin{aligned} \sum_{i,j}c_i c_jK(x_i,x_j) &=\sum_{i,j}c_i c_j \langle\phi(x_i),\phi(x_j)\rangle\\ &=\left\lVert\sum_i c_i\phi(x_i)\right\rVert^2\\ &\geq0. \end{aligned} \]

Portanto, 2 não é um detalhe técnico arbitrário: ela decorre do fato de que o quadrado de uma norma nunca é negativo.

6.4.6 Mercer e o espaço associado

Em linguagem comum de aprendizado de máquina, a condição anterior é frequentemente chamada “condição de Mercer”. Convém, porém, separar dois resultados relacionados:

o teorema de Moore–Aronszajn garante que todo núcleo simétrico e semidefinido positivo determina um espaço de Hilbert de funções com núcleo reprodutor e um mapa de atributos, possivelmente infinito-dimensional;
o teorema de Mercer, sob hipóteses adicionais como domínio compacto e núcleo contínuo, simétrico e positivo, fornece uma expansão espectral em autofunções.

Em uma forma simplificada, a expansão de Mercer é

\[ K(x,z)=\sum_{r=1}^{\infty}lambda_r e_r(x)e_r(z), \qquad \lambda_r\geq0, \]

onde \(e_r\) são autofunções ortonormais de um operador integral associado ao núcleo. Isso sugere o mapa

\[ \phi(x)= \left(\sqrt{\lambda_1}e_1(x), \sqrt{\lambda_2}e_2(x),\ldots\right), \]

pois seu produto escalar recupera \(K(x,z)\). O espaço pode ter dimensão infinita, mas o algoritmo acessa apenas avaliações do núcleo.

Semidefinido não significa estritamente positivo

É permitido que \(c^{\mathsf T}Gc=0\) para algum vetor não nulo \(c\). Isso ocorre quando os vetores transformados possuem dependência linear. Um núcleo semidefinido positivo continua sendo válido nesse caso.

6.4.7 Regras para construir novos núcleos

Se \(K_1\) e \(K_2\) são núcleos válidos e \(a,b\geq0\), então também são válidos:

\[ aK_1(x,z)+bK_2(x,z), \qquad K_1(x,z)K_2(x,z). \]

Além disso, para qualquer função \(q:X\to\mathbb R\),

\[ K(x,z)=q(x)q(z) \]

é um núcleo válido. Essas regras permitem combinar noções de similaridade sem precisar descobrir explicitamente o mapa resultante. Subtrair núcleos ou aplicar uma transformação arbitrária, por outro lado, pode destruir a semidefinição positiva.

6.4.8 Verificação numérica em uma amostra

import numpy as np


def verificar_gram(G, tolerancia=1e-10):
    G = np.asarray(G, dtype=float)
    if G.ndim != 2 or G.shape[0] != G.shape[1]:
        raise ValueError("G deve ser uma matriz quadrada")

    simetrica = np.allclose(G, G.T, atol=tolerancia)
    G_sim = (G + G.T) / 2
    autovalores = np.linalg.eigvalsh(G_sim)
    psd = autovalores.min() >= -tolerancia
    return simetrica, psd, autovalores

Esse teste verifica apenas a matriz dos pontos fornecidos. Ele pode encontrar um contraexemplo e provar que uma função não é um núcleo válido, mas resultados positivos em algumas amostras não demonstram a propriedade para todo conjunto finito possível. A validade geral exige uma prova ou um resultado teórico conhecido.

6.4.8.1 Exercícios

Prove diretamente que \(K(x,z)=x^{\mathsf T}z\) satisfaz
Mostre que a soma de dois núcleos válidos com coeficientes não negativos também é válida.
Dê um exemplo de matriz simétrica que não seja semidefinida positiva.
Explique por que testar apenas uma matriz de Gram não prova que uma função é núcleo em todo o domínio.
Qual é o mapa de atributos associado a \(K(x,z)=1+x^{\mathsf T}z\)?

6.4.9 Vantagem

O artifício do núcleo permite trabalhar com uma geometria não linear sem armazenar explicitamente todos os atributos de \(\phi(x)\). Suas principais vantagens são:

representar interações de dimensão muito alta com uma fórmula curta;
reutilizar algoritmos baseados em produtos escalares;
expressar diferentes noções de similaridade por meio da escolha de \(K\);
obter fronteiras não lineares mantendo uma otimização convexa em métodos como a SVM.

Essas vantagens não eliminam os custos. O treinamento normalmente usa a matriz de Gram \(N\times N\), e uma predição por Equation 6.9 pode exigir uma avaliação do núcleo para cada coeficiente \(\alpha_i\) não nulo. Em uma SVM, apenas os exemplos com \(\alpha_i\neq0\) são vetores de suporte, o que pode tornar a predição esparsa; ainda assim, seu número depende dos dados e dos hiperparâmetros.

6.4.10 Núcleo linear

\[ K(x,z)=x^{\mathsf T}z. \]

Ele não cria uma fronteira não linear: corresponde ao mapa identidade. Serve como referência e costuma ser competitivo quando os atributos já são numerosos, como em representações esparsas de texto.

6.4.11 Núcleo polinomial

\[ K(x,z)=(\gamma x^{\mathsf T}z+c_0)^Q, \]

com \(\gamma>0\), \(c_0\geq0\) e grau inteiro \(Q\geq1\). O núcleo representa monômios e interações até o grau \(Q\) quando \(c_0>0\). Se \(c_0=0\), contém somente termos de grau exatamente \(Q\). Os parâmetros \(\gamma\) e \(c_0\) alteram a escala relativa das contribuições e devem ser tratados como parte do modelo.

6.4.12 Núcleo gaussiano ou RBF

\[ K(x,z) =\exp\!\left(-\gamma\lVert x-z\rVert^2\right) =\exp\!\left(-\frac{\lVert x-z\rVert^2}{2\sigma^2}\right), \]

onde

\[ \gamma=\frac1{2\sigma^2}. \]

O núcleo RBF vale \(1\) quando \(x=z\) e se aproxima de zero à medida que a distância cresce. Seu mapa de atributos é infinito-dimensional, mas a avaliação do núcleo depende apenas da distância euclidiana.

O parâmetro controla a escala da vizinhança:

\(\gamma\) pequeno (ou \(\sigma\) grande): a similaridade decai lentamente e a fronteira tende a variar suavemente;
\(\gamma\) grande (ou \(\sigma\) pequeno): a influência de cada ponto fica localizada e a fronteira pode se tornar muito irregular.

Na SVM, \(\gamma\) interage com o parâmetro de regularização \(C\). Valores altos de \(C\) penalizam fortemente violações na amostra; valores menores aceitam mais violações para favorecer uma margem regularizada. Ambos devem ser escolhidos com validação, nunca pelo desempenho no teste.

A escala dos atributos muda o núcleo RBF

Uma variável medida em milhares pode dominar \(\lVert x-z\rVert^2\) e anular a influência de variáveis medidas entre zero e um. Ajuste a padronização somente no treino e aplique os mesmos parâmetros aos demais dados.

6.4.13 Escolha prática

Uma sequência razoável é começar pelo núcleo linear, estabelecer uma linha de base e só então testar uma geometria não linear. Para o RBF, buscamos \(C\) e \(\gamma\) em escala logarítmica por validação cruzada. Para o polinomial, grau, \(C\), \(\gamma\) e \(c_0\) ampliam o espaço de busca e exigem maior cuidado.

Também é necessário considerar o tamanho da amostra. Quando \(N\) é muito grande e um mapa explícito moderado existe, um método linear sobre os atributos transformados ou uma aproximação de núcleo pode ser mais eficiente que armazenar a matriz de Gram completa.

import numpy as np


def kernel_rbf(X, Z, gamma):
    X = np.asarray(X, dtype=float)
    Z = np.asarray(Z, dtype=float)
    if gamma <= 0:
        raise ValueError("gamma deve ser positivo")

    norma_X = np.sum(X**2, axis=1)[:, None]
    norma_Z = np.sum(Z**2, axis=1)[None, :]
    dist2 = np.maximum(norma_X + norma_Z - 2 * X @ Z.T, 0.0)
    return np.exp(-gamma * dist2)

A correção com maximum remove pequenos valores negativos de distância quadrática causados por arredondamento. O resultado possui formato (len(X), len(Z)), útil tanto para a matriz de treino quanto para comparar novos exemplos aos exemplos armazenados.

6.4.13.1 Exercícios

Calcule o núcleo RBF para pontos iguais e interprete o resultado.
Descreva o efeito de \(\gamma\to0\) e de \(\gamma\to\infty\) para pontos distintos.
Explique por que a padronização influencia o RBF, mas não corrige por si só sobreajuste.
Compare o custo de armazenar \(N\times d'\) com \(N\times N\) em dois cenários escolhidos por você.
Por que um bom resultado com núcleo linear é uma referência útil antes de testar núcleos mais flexíveis?

6.4.14 Aplicações

O uso sistemático de funções núcleo antecede as SVMs modernas, mas ganhou grande visibilidade com os classificadores de margem na década de 1990. A ideia, entretanto, não pertence a um único algoritmo: sempre que um método admite uma formulação baseada em produtos escalares, podemos investigar uma versão com núcleo.

6.4.15 Máquinas de vetores de suporte

Na forma dual de uma SVM, o treinamento utiliza os exemplos por meio de

\[ y_i y_j K(x_i,x_j). \]

Depois do ajuste, a função de decisão é

\[ f(x)=\sum_{i\in\mathcal S}\alpha_i y_iK(x_i,x)+b, \]

onde \(\mathcal S\) é o conjunto de vetores de suporte. A classificação é \(\operatorname{sinal}(f(x))\). O núcleo altera a geometria na qual a margem é maximizada, enquanto \(C\) controla a penalização das violações.

6.4.16 Regressão com núcleo

Na regressão ridge com núcleo, buscamos uma função da forma

\[ f(x)=\sum_{i=1}^N\alpha_iK(x_i,x). \]

Com perda quadrática e regularização, os coeficientes satisfazem

\[ (G+\lambda I)\alpha=y, \]

em que \(G\) é a matriz de Gram e \(\lambda>0\) controla a regularização. A adição de \(\lambda I\) também melhora a estabilidade numérica quando \(G\) é singular ou quase singular.

6.4.17 PCA com núcleo

A análise de componentes principais comum encontra direções lineares de maior variância. A PCA com núcleo efetua a análise no espaço \(\mathcal F\) sem formar explicitamente \(\phi(x)\). Para isso, trabalha com uma matriz de Gram centralizada:

\[ G_c=HGH, \qquad H=I-\frac1N\mathbf1\mathbf1^{\mathsf T}. \]

Centralizar os atributos originais não substitui essa operação: o que precisa ter média zero são os vetores \(\phi(x_i)\) no espaço de atributos. Os autovetores de \(G_c\) fornecem coordenadas não lineares úteis para visualização e redução de dimensionalidade.

6.4.18 Dados estruturados e núcleos especializados

O domínio não precisa ser \(\mathbb R^d\). É possível definir núcleos para sequências, árvores, grafos, conjuntos ou histogramas, desde que a função resultante seja simétrica e semidefinida positiva. Nesses casos, o núcleo incorpora conhecimento sobre a estrutura do objeto e permite aplicar um método geométrico sem converter tudo para um vetor denso de tamanho fixo.

Em texto, por exemplo, o núcleo linear sobre vetores esparsos de frequência é uma base forte. Núcleos mais elaborados podem comparar subsequências, mas seu custo e a dificuldade de escolher hiperparâmetros precisam ser comparados a representações explícitas modernas.

6.4.19 Um roteiro de decisão

Antes de adotar um método com núcleo, responda:

O método possui uma formulação baseada em produtos escalares?
Há uma noção de similaridade adequada ao domínio e comprovadamente válida como núcleo?
O número \(N\) de exemplos permite armazenar e processar \(N^2\) valores?
A predição terá latência aceitável com a quantidade esperada de exemplos ativos ou vetores de suporte?
Há validação para escolher o núcleo e seus hiperparâmetros sem usar o conjunto de teste?

Se \(N\) for muito grande, alternativas incluem mapas explícitos de baixa dimensão, aproximações por características aleatórias, métodos de Nyström e modelos lineares ou neurais treinados em lotes. O núcleo é uma ferramenta poderosa, não uma etapa obrigatória.

6.4.20 Exemplo de fluxo experimental

# Pseudocódigo: a sintaxe exata depende da biblioteca utilizada.
separar_treino_validacao_teste()

for nome_kernel, parametros in configuracoes:
    for particao_treino, particao_validacao in validacao_cruzada(treino):
        normalizador.ajustar(particao_treino.X)
        Xtr = normalizador.transformar(particao_treino.X)
        Xva = normalizador.transformar(particao_validacao.X)

        modelo = SVM(kernel=nome_kernel, **parametros)
        modelo.ajustar(Xtr, particao_treino.y)
        registrar(modelo.avaliar(Xva, particao_validacao.y))

escolher_configuracao_por_validacao()
avaliar_uma_vez_no_teste()

O normalizador é reajustado em cada partição para evitar vazamento. A avaliação final no teste é realizada uma única vez, depois que todas as decisões de modelagem foram encerradas.

6.4.20.1 Exercícios

Identifique onde o núcleo aparece na predição de uma SVM.
Explique por que \(G+\lambda I\) é numericamente mais estável que \(G\) quando alguns autovalores são próximos de zero.
Derive a matriz \(H\) para \(N=3\) e verifique que \(H\mathbf1=0\).
Proponha uma função de similaridade para um domínio estruturado e discuta o que faltaria provar para usá-la como núcleo.
Em que cenário um mapa explícito pode ser preferível à matriz de Gram?

6.4.21 Síntese do capítulo

Transformar atributos permite converter relações não lineares no espaço original em relações lineares em outro espaço. Mapas polinomiais tornam essa construção concreta, mas sua dimensão cresce combinatoriamente. O artifício do núcleo evita materializar o mapa quando o algoritmo depende somente de produtos escalares. Em troca, desloca o custo para a matriz de Gram e para as avaliações de similaridade. A escolha entre mapa explícito e núcleo deve considerar expressividade, generalização, memória, tempo de treinamento e custo de predição.

6.5 Exercícios de múltipla escolha

As questões integram transformação de atributos, mapas polinomiais e métodos de núcleo. Há somente uma alternativa correta em cada item.

Ao aplicar \(\phi(x_1,x_2)=(x_1^2,x_2^2)\), a fronteira linear \(w_1z_1+w_2z_2+b=0\) no espaço transformado corresponde, no espaço original, a uma fronteira:
1. necessariamente linear.
2. quadrática.
3. cúbica.
4. independente de \(x_1\) e \(x_2\).
Depois de uma transformação não linear \(\phi\), chamar o modelo de linear significa que ele é linear:
1. nos atributos transformados e em seus parâmetros.
2. em qualquer variável do problema original.
3. apenas no número de exemplos.
4. somente no tempo de execução.
Quantos monômios de grau total até \(p\) existem em \(d\) variáveis, incluindo o termo constante?
1. \(dp\).
2. \(d+p\).
3. \(\binom{d+p}{p}\).
4. \(2^{dp}\) em todos os casos.
Aumentar o grau de um mapa polinomial tende a:
1. reduzir sempre a capacidade e o custo.
2. aumentar expressividade e também o risco de sobreajuste.
3. preservar exatamente a mesma classe de hipóteses.
4. garantir erro de teste zero.
O artifício do núcleo é aplicável quando o algoritmo pode ser escrito em termos de:
1. produtos escalares entre exemplos transformados.
2. ordenação alfabética dos atributos.
3. apenas uma coordenada por exemplo.
4. operações bit a bit.
Uma função núcleo válida satisfaz \(k(x,z)=\langle\phi(x),\phi(z)\rangle\) para algum mapa de atributos. Consequentemente, sua matriz de Gram deve ser:
1. antissimétrica.
2. triangular com diagonal nula.
3. simétrica e semidefinida positiva.
4. composta somente por números inteiros.
Qual expressão define o núcleo RBF?
1. \(x^{\mathsf T}z\).
2. \((x^{\mathsf T}z+c)^p\).
3. \(\exp(-\gamma\|x-z\|^2)\).
4. \(\|x+z\|\).
No núcleo RBF, um valor muito alto de \(\gamma\) geralmente torna a similaridade:
1. mais local, decaindo rapidamente com a distância.
2. constante e igual a um.
3. independente dos dados.
4. necessariamente negativa.
Uma limitação importante de métodos que armazenam uma matriz de Gram densa para \(N\) exemplos é o consumo de memória de ordem:
1. \(O(1)\).
2. \(O(\log N)\).
3. \(O(N)\).
4. \(O(N^2)\).
A escolha de hiperparâmetros como grau, \(\gamma\) ou regularização deve ser realizada principalmente com:
1. o conjunto de teste final.
2. dados de validação ou validação cruzada.
3. exemplos inventados após conhecer o teste.
4. somente o erro de treinamento.

Gabarito comentado

b. Substituir \(z_1=x_1^2\) e \(z_2=x_2^2\) produz uma equação de segundo grau nas coordenadas originais.
a. A fronteira é linear em \(\phi(x)\) e nos pesos, embora possa ser curva em \(x\).
c. A contagem de combinações com repetição resulta em \(\binom{d+p}{p}\).
b. Mais termos permitem ajustar padrões mais complexos, mas elevam capacidade, custo e sensibilidade à amostra.
a. O núcleo substitui diretamente \(\langle\phi(x),\phi(z)\rangle\) sem materializar \(\phi\).
c. Essa é a condição que permite interpretar a função como produto interno em um espaço de atributos.
c. O RBF decai exponencialmente com a distância quadrática.
a. Quanto maior \(\gamma\), menor a escala espacial de influência de cada exemplo.
d. A matriz contém uma similaridade para cada par de exemplos.
b. O teste deve permanecer intocado; a validação orienta as decisões de modelagem.